package com.dataStructure.tree;


import java.util.*;

/**
 * 二叉搜索树的逻辑：就是中序遍历的结果一定是从小到大，即左中右。
 *  二叉树的递归遍历，根本上都是从上到下，只是我们处理节点的顺序不同，造就了前序遍历，中序遍历，后序遍历
 *
 *  构造二叉树：首先要明确，如何确定一颗二叉树
 *     前序，后序两者之一，再加上中序遍历即可确定唯一二叉树，而前序，后序，不可以，因为二叉树的左右位置无法确定
 *     现在，我以前序和后序分布讲解一下
 *
 *    1.找到后序数组的最后一位
 *    2. 以其为切割点，将中序数组一分为二，（左中序数组，右中序数组）
 *
 *
 *
 */

public class BinaryTree {

    public static void main(String[] args) {

        int[] ints = {1, 2, 3, 4, 5};
        int[] ints1 = Arrays.copyOfRange(ints, 1, 5);
        System.out.println(Arrays.toString(ints1));

        Deque<Integer> deque = new LinkedList<>();


    }

    /**
     * 二叉搜索树的最小k个
     * @param root
     * @param k
     */
    int count = 0;
    int res=0;
    public void minKBinaryTree(TreeNode root, int k) {
        if (root == null) {
            return;
        }
        minKBinaryTree(root.left, k);
        count++;
        if (k == count) {
            res  = root.val;
            return;
        }

        minKBinaryTree(root.right, k);

    }

    /**
     * 二叉搜索树的插入操作
     */
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }

        TreeNode cur = root;
        while (true) {
            //比较是否为右树
            if (val > cur.val) {
                if (cur.right != null)
                    cur = cur.right;
                else {
                    cur.right = new TreeNode(val);
                    break;
                }
            }
            //比较是否为左树
            if (val < cur.val) {
                if (cur.left != null)
                    cur = cur.left;
                else {
                    cur.left = new TreeNode(val);
                    break;
                }
            }
        }
        return root;
    }

    /**
     *  从中序遍历，前序遍历，构造二叉树
     */
    public static TreeNode travel(int[] inorder, int[] postorder) {
        if (postorder.length == 0) {
            return null;
        }
        int value = postorder[postorder.length -1];
        TreeNode root = new TreeNode(value);
        if (postorder.length == 1) {
            return root;
        }

        //找到中序数组的切割点
        int i;
        for ( i = 0 ;i < inorder.length ;i++) {
            if (value == inorder[i])
                break;
        }
        int[] leftInorder = Arrays.copyOf(inorder, i);
        int[] rightInorder = Arrays.copyOfRange(inorder, i + 1, inorder.length);

        //删除后续数组的最后一位
        postorder = Arrays.copyOf(postorder,postorder.length -1);
        //得到后序左数组
        int[] leftPostorder = Arrays.copyOf(postorder, leftInorder.length);
        //得到后序右数组
        int[] rightPostorder = Arrays.copyOfRange(postorder, leftInorder.length , postorder.length);

        //
        root.left = travel(leftInorder,leftPostorder);
        root.right = travel(rightInorder,rightPostorder);
        return root;

    }






    /**
     *
     * @param root
     * @return
     */
    public int[] findMode(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return new int[0];
        }
        diGui5(root,list);
        List<Integer> list2 = new ArrayList<>();
        int max = Integer.MIN_VALUE;
        int sum = 0;
        for (int i = 1 ; i < list.size(); i++) {
            if (list.get(i - 1).equals(list.get(i))) {
                sum += list.get(i);
                continue;
            }
            //开始新的众数
            else {
                if (sum > max) {
                    for (int j = 0 ; j  < list2.size() ;j ++) {
                        if (list2.get(j).equals(max)) {
                            list.remove(j);
                        }
                    }
                    //将众数添加到数组，并且刷新 max
                    max = sum;
                    list2.add(list.get(i-1));
                }
                else if (sum == max) {
                    //将众数添加到数组
                    list2.add(list.get(i-1));
                }
                else {

                }

                sum = 0;
                sum += list.get(i);
            }
        }

        Integer[] integers = list2.toArray(new Integer[list2.size()]);

        return Arrays.stream(integers).mapToInt(Integer::valueOf).toArray();

    }

    public static void diGui5(TreeNode cur,List<Integer> list) {
        if (cur == null) {
            return;
        }
        diGui5(cur.left,list);
        list.add(cur.val);
        diGui5(cur.right,list);

    }

    /**
     *  二叉搜索树的最小绝对差
     * @param root
     * @return
     */
    static int min = Integer.MIN_VALUE;
    public int getMinimumDifference(TreeNode root) {
        if (root == null) {
            return 0;
        }
        ArrayList<Integer> list = new ArrayList<>();
        diGui4(root,list);
        for(int i = 0 ;i < list.size() -1; i++) {
            int value = list.get(i+1) - list.get(i);
            if (value > min)
                min = value;
        }
        return min;
    }

    public static void diGui4(TreeNode cur,List<Integer> list) {

        diGui4(cur.left,list);
        if (cur == null) {
            return;
        }
        list.add(cur.val);
        diGui4(cur.right,list);

    }


    /**
     * 98：验证二叉搜索树
     * @param root
     * @return
     */
    public boolean isValidBST(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();

        diGui3(root,list);
        for (int i = 1 ; i < list.size() ;i++) {
            if (list.get(i-1)  > list.get(i)) {
                return false;
            }
        }
        return true;
    }

    public static void diGui3(TreeNode cur,List<Integer> list) {

        diGui3(cur.left,list);
        if (cur == null) {
            return;
        }
        list.add(cur.val);
        diGui3(cur.right,list);
    }

    /**
     * 力扣700：二叉搜索树的的搜索
     * @param root
     * @param val
     * @return
     */
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null) {
            return null;
        }
        TreeNode cur = root;
        while (cur != null) {
            if (cur.val == val) {
                return cur;
            }

            if (val > cur.val) {
                cur = cur.right;
            }
            if (val < cur.val) {
                cur = cur.left;
            }

        }

        return null;

    }


    /**
     * 112. 路径总和
     * @param root
     * @param targetSum
     * @return
     */
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        return diGui1(root,targetSum);

    }

    public static boolean diGui1(TreeNode cur,int num) {

        //到达叶子节点了
        if (cur.left == null && cur.right == null) {
            if (num == 0) {
                return true;
            } else
                return false;
        }

        if (cur.left != null) {
            num -= cur.left.val;
            boolean result = diGui1(cur.left, num);
            if (result)
                return true;
            else
                num+=cur.left.val;
        }

        if (cur.right != null) {
            num -= cur.right.val;
            boolean result2 = diGui1(cur.right, num);
            if (result2)
                return true;
            else
                num += cur.right.val;
        }

        return false;
    }

    /**
     * 力扣 513：找到树左下角的值
     * @param root
     * @return
     */
    public int findBottomLeftValue(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        int value = 0;
        if (root == null) {
            return 0;
        }
        queue.offer(root);

        while (queue.size() != 0) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode poll = queue.poll();
                if (i == 0) {
                    value = poll.val;
                }

                if (poll.left != null) {
                    queue.offer(poll.left);
                }

                if (poll.right != null) {
                    queue.offer(poll.right);
                }
            }
        }

        return value;
    }

    /**
     * 力扣 404：左叶子之和
     * @param root
     * @return
     */
    public int sumOfLeftLeaves(TreeNode root) {
        int sum = 0;
        if (root == null) {
            return 0;
        }
        diGui(root,sum);
        return sum;

    }


    public static void diGui(TreeNode cur,int sum) {
        if (cur.left != null && cur.left.left == null && cur.right.right == null) {
            sum += cur.left.val;
            return;
        }
        diGui(cur.left,sum);
        diGui(cur.right,sum);
    }

    /**
     * 力扣257，二叉树的所有路径
     * @param root
     * @return
     */
    public List<String> binaryTreePaths(TreeNode root) {
        ArrayList<String> result = new ArrayList<>();
        ArrayList<Integer> path = new ArrayList<>();

        if (root == null) {
            return result;
        }
        travelsal(path,result,root);
        return result;
    }


    public static void travelsal(List<Integer> path,List<String> result,TreeNode cur) {
        path.add(cur.val);

        if (cur.right == null && cur.left == null) {
            StringBuilder builder = new StringBuilder();
            for (int i = 0 ;i < path.size() -1 ; i++){
                builder.append(path.get(i))
                        .append("->");
            }
            builder.append(cur.val);
            result.add(builder.toString());

            return;
        }

        if (cur.left!= null) {
            travelsal(path,result,cur.left);
            path.remove(cur.left.val);
        }

        if (cur.right != null) {
            travelsal(path,result,cur.right);
            path.remove(cur.right.val);
        }



    }

    /**
     * 力扣 222  完全二叉树的节点个数
     * @param root 根节点
     * @return 个数
     */
    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int ct = 0;

        while (queue.size() != 0) {

            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode poll = queue.poll();
                ct++;
                if (poll.left != null) {
                    queue.offer(poll.left);
                }
                if (poll.right != null) {
                    queue.offer(poll.right);
                }
            }
        }
        return ct;
    }

    /**
     * 力扣101：对称二叉树
     * @param root 根节点
     * @return 是否为对称二叉树
     */
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root.left);
        queue.offer(root.right);

        while (!queue.isEmpty()) {
            TreeNode node1 = queue.poll();
            TreeNode node2 = queue.poll();
            if (node1 == null && node2 == null) {
                continue;
            }
            if (node1 == null || node2 == null || node1.val != node2.val) {
                return false;
            }
            queue.offer(node1.left);
            queue.offer(node2.right);
            queue.offer(node1.right);
            queue.offer(node2.left);
        }

        return true;

    }

    /**
     * 226 翻转二叉树
     * @param root
     * @return
     */
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }

        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (queue.size() != 0) {
            int size = queue.size();
            for (int i = 0;i < size; i++) {
                TreeNode poll = queue.pollFirst();
                //交换左右节点
                TreeNode temp;
                temp = poll.left;
                poll.left = poll.right;
                poll.right = temp;
                if (poll.left != null) {
                    
                    queue.offer(poll.left);
                }
                if (poll.right != null) {
                    queue.offer(poll.right);
                }

            }
        }

        return root;
    }

    /**
     * 连接二叉树
     * @param root
     * @return
     */
    public Node2 connect(Node2 root) {
        if (root == null) {
            return null;
        }
        Queue<Node2> queue = new LinkedList<>();
        queue.offer(root);

        while (queue.size() != 0) {
            int size = queue.size();

            Node2 cur = null;
            Node2 next;
            for (int i = 0; i < size; i++) {
                Node2 poll = queue.poll();

                if (poll.left != null) {
                    queue.offer(poll.left);
                }
                if (poll.right != null) {
                    queue.offer(poll.right);
                }

                if (cur != null) {
                    next = poll;
                }
                cur = poll;
                next = poll.next;
            }
        }
        return root;
    }


    /**
     * 查找某一行的最大值
     * @param root
     * @return
     */
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (queue.size() != 0) {
            int size = queue.size();
            List<Integer>  list1 = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode cur = queue.poll();
                list1.add(cur.val);
                if (cur.left != null) {
                    queue.offer(cur.left);

                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }

            Integer max = Collections.max(list1);
            list.add(max);
        }
        return list;
    }

    /**
     * 二叉树的层序遍历2 力扣 107,   这里每一个for 循环  都代表一行,
     *  思路：借助队列，按照从上到下，从左到右的
     */
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> listD = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if (root == null) {
            return listD;
        }
        queue.offer(root);

        while (queue.size() != 0) {
            int size = queue.size();
            List<Integer> list = new ArrayList<>(2);
            for (int i = 0 ;i < size; i++) {
                TreeNode cur = queue.poll();
                list.add(cur.val);

                if (cur.left != null)
                    queue.offer(cur.left);
                if (cur.right != null)
                    queue.offer(cur.right);

            }
            listD.add(list);
        }
        Collections.reverse(listD);
        return listD;
    }








    /**
     * 二叉树的层序遍历
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> listD = new ArrayList<>();
        if (root == null) {
            return listD;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (queue.size() != 0) {

            ArrayList<Integer> list = new ArrayList<>(2);
            int size = queue.size();


            for (int i = 0 ;i < size ;i++) {
                TreeNode poll = queue.poll();
                list.add(poll.val);
                if (poll.left != null) {
                    queue.offer(poll.left);
                }
                if (poll.right != null) {
                    queue.offer(poll.right);
                }
            }

            listD.add(list);

        }

        return listD;

    }

    /**
     * 二叉树的迭代遍历
     * @param root 根节点
     * @return 二叉树前序遍历的结果
     */
    public List<Integer> preorderTraversal1(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        if (root == null) {
            return list;
        }
        stack.push(root);
        while (stack.size() != 0) {
            TreeNode cur =  stack.peek();
            stack.pop();
            list.add(cur.val);
            if (cur.right != null) {
                stack.push(cur.right);
            }
            if (cur.left != null) {
                stack.push(cur.left);
            }

        }
        return list;
        
    }
    /**
     * 二叉树  中序遍历  左中右的顺序
     * 第一步，遍历到二叉树左节点，然后再到
     * @param root  根节点，
     * @return  集合的顺序就是中序遍历的顺序
     */
    public List<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        zhong(root,list);
        return list;
    }

    public void zhong(TreeNode root, ArrayList<Integer> list) {
        if (root == null) {
            return;
        }
        zhong(root.left,list);
        list.add(root.val);
        zhong(root.right,list);
    }

    /**
     * 二叉树的前序遍历      通过递归的方式   从整体上就是先遍历完左边，再遍历右边
     *
     *  中左右的顺序，
     * @param cur 根节点，
     * @param list 遍历集合
     */
    public List<Integer> preForEach(TreeNode cur , List<Integer> list) {
        pre(cur,list);
        return list;
    }

    private void pre(TreeNode cur, List<Integer> list) {
        //如果下一个节点指向为空，则便利结束
        if (cur == null) {
            return;
        }
        //将当前节点添加到遍历集合
        list.add(cur.val);
        //接着将下一个左儿子添加到集合，
        pre(cur.left,list);
        pre(cur.right,list);

    }





}
